НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені  ІГОРЯ СІКОРСЬКОГО”                     ЗВІТ з лабораторної роботи №6 з навчальної дисципліни “Програмування складних алгоритмів”             Тема: «Розріджені матриці» Варіант 18              Мета: Метою лабораторної роботи є ознайомитися з основами роботи з розрідженими матрицями. Теоретична частина На практицi зустрiчаються масиви, якi через певнi причини можуть займати пам’ять не повнiстю, а частково. Це особливо актуально для масивiв великих розмiрiв, таких що для їхнього збереження в повному об’ємi може бути не достатньо пам’ятi комп’ютера. Розрiджений масив – це масив, бiльшiсть елементiв якого рiвнi мiж собою, так що зберiгати достатньо лише невелику кiлькiсть значень, вiдмiнних вiд основного (фонового) значення. Нема єдиного визначення, яка кiлькiсть ненульових елементiв має бути в матрицi, щоб вона була розрiдженою. При роботi iз розрiдженими масивами питання розташування їх в пам’ятi реалiзуються на логiчному рiвнi з врахуванням типу елементiв. Простим прикладом роботи iз розрiдженими масивами можуть бути електроннi таблицi: попри те, що робочий лист документу має розмiр 16384 × 1048576 елементiв (для Excel 2010) зайнятими є не бiльше 1 вiдсотка вiд потенцiйно доступних комiрок. Розрiзняють два типи розрiджених масивiв: • масиви, в яких розташування елементiв зi значеннями, вiдмiнними вiд фонового, можуть бути описанi математично; • масиви з випадковим розташуванням елементiв. До масивiв з математичним описом розташування елементiв вiдносяться масиви, в яких iснують функцiональнi закономiрностi в розташуваннi елементiв iз значеннями, вiдмiнними вiд фонового. Елементи, значення яких є фоновими, називають нульовими. Елементи, значення яких вiдмiннi вiд фонового називають ненульовими. Фонове значення не обов’язково рiвне нулю. Ненульовi значення зберiгаються, як правило, в одновимiрному масивi, а зв’язок мiж розташуванням у розрiдженому масивi i в новому, одновимiрному, описується математично за допомогою формули, що перетворює iндекси масиву в iндекси вектора. На практицi для роботи з розрiдженим масивом розробляються функцiї: • для перетворення iндексiв масиву в iндекс вектора; • для отримання значення елемента масиву з його упакованого представлення за iндексами; • для запису значення елемента масиву в її упаковане представлення за iндексами. До масивiв з випадковим розташуванням елементiв вiдносяться масиви, в яких не iснує закономiрностей у розташуваннi елементiв iз значеннями, вiдмiнними вiд фонового. Один з основних способiв збереження подiбних розрiджених матриць полягає у збереженнi ненульових елементiв в одновимiрному масивi iз iдентифiкацiєю кожного елемента масиву iндексами. Спосiб послiдовного розподiлу має також ту перевагу, що операцiї над матрицями можуть бути виконанi швидше, нiж це можливо при представленнi у виглядi послiдовного масиву, особливо якщо розмiр матрицi великий. Пам’ять, необхiдна для збереження розрiджених матриць, складається з двох частин: основної пам’ятi, у якiй розмiщуються числовi значення елементiв та додаткової пам’ятi, де зберiгаються iндекси та iнша iнформацiя, необхiдна для формування структури матриць i яка забезпечує доступ до числових значень їх елементiв. Способи зберiгання i використання даних, що зберiгаються в основнiй i додатковiй пам’ятi, досить рiзноманiтнi i визначаються, головним чином, обраним методом. Якщо елементами масиву є цiлi числi, то найпростiший пiдхiд полягає у створеннi двомiрного масиву розмiрностi n ∗ 3, де n - кiлькiсть ненульових елементiв вихiдної розрiдженої матрицi. Першi два елементи кожного рядка мiстять iндекси рядка та стовпця ненульового елементу, а третiй - значення самого елементу. Завдання до лабораторної роботи: 1 Розробити спосіб економного зберігання в пам’яті розріджених матриць. 2 Виконати індивідуальне завдання над стисненою матрицею. 3 Вивести матрицю до та після обробки у стисненому та розгорнутому вигляді. 18. Обнулити мінімальні ел...